package com.hardy.leecode;

/**
 * Author: Hardy
 * Date:   2020/6/28
 * Description:
 * - 寻找两个正序数组的中位数
 * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 * <p>
 * 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * <p>
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * nums1 = [1, 3]
 * nums2 = [2]
 * <p>
 * 则中位数是 2.0
 * 示例 2:
 * <p>
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 * <p>
 * 则中位数是 (2 + 3)/2 = 2.5
 * <p>
 * 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
 **/
public class Que4 {
    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 2};
        int[] nums2 = new int[]{3, 4};

        System.out.println(new Solution().findMedianSortedArrays(nums1, nums2));
    }

    static class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int l1 = nums1.length;
            int l2 = nums2.length;

            if (l1 == 0 && l2 == 0) return 0;

            // 偶数奇数 和 中间位置 + 1
            int is = (l1 + l2) % 2;
            int mid = (l1 + l2) / 2 + 1;

            // 特殊处理
            if (l1 == 0 || l2 == 0) {
                int[] nums = l1 == 0 ? nums2 : nums1;
                return is == 1 ? nums[mid - 1] : (0.0 + nums[mid - 2] + nums[mid - 1]) / 2;
            }

            // 双指针
            int i = 0;
            int j = 0;
            int m = 0;
            int n = 0;
            int idx = 0;

            while (true) {
                if (i >= l1) {
                    m = n;
                    n = nums2[j++];
                } else if (j >= l2) {
                    m = n;
                    n = nums1[i++];
                } else {
                    int a = nums1[i];
                    int b = nums2[j];

                    if (a >= b) {
                        j++;
                        m = n;
                        n = b;
                    } else {
                        i++;
                        m = n;
                        n = a;
                    }
                }
                if (++idx == mid) return is == 1 ? n : (0.0 + m + n) / 2;
            }
        }
    }
}
